#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//todo 怎么能用背包呢 我擦啊


/*
 *
只有确定了如下四点，才能把01背包问题套到本题上来。
1 背包的体积为sum / 2
2 背包要放⼊的商品（集合⾥的元素）重量为 元素的数值，价值也为元素的数值
3 背包如何正好装满，说明找到了总和为 sum / 2 的⼦集。
4 背包中每⼀个元素是不可重复放⼊。
以上分析完，我们就可以套⽤01背包，来解决这个问题了
 背包体积为 sum/2
 放入的商品体积为 nums[i]
 j 代表下标
 问 背包体积为sum/2下最大装的物品体积

 *
 * **/
//可以改为 那么只要找到集合⾥能够出现 sum / 2 的⼦集总和，就算是可以分割成两个相同元素和⼦集了

//dp[j] j代表 [0,sum/2]  因为规定了长度 所以也不会超过200的 i代表对应的价值
//
bool canPartition(vector<int> &nums) {

    int sumDv2 = 0;

    for (int i = 0; i < nums.size(); ++i) {
        sumDv2 += nums[i];
    }
    if (sumDv2 % 2 != 0)
        return false;

    sumDv2 = sumDv2 / 2;

    vector<int> dp(10001, 0);

    //循环物品
    for (int i = 0; i < nums.size(); ++i) {

        //这里是>= nums[i] 背包体积大于货物体积才行
        for (int j = sumDv2; j >= nums[i]; --j) {
            //这边从大到小的原因是因为 第一个状态用的还是第一个dp状态的导致出问题加了两次了
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }


    }


    return dp[sumDv2] == sumDv2;

}

